/**
 * 项目名称: 线索二叉树.cpp
 * 项目路径: study/DataStructure/数据结构/树/二叉树
 * 编辑时间: 2024年08月04日17时24分13秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

typedef struct ThreadNode {
    int data;
    struct ThreadNode *lChild,*rChild;//左,右孩子指针
    int lTag,rTag;//左,右线索标志
}ThreadNode,*ThreadTree;

/**
 * 中序遍历二叉线索树
 * @param p
 * @param pre
 */
void InThread(ThreadTree &p,ThreadTree &pre){
    if(p!= nullptr){
        InThread(p->lChild,pre);//递归,线索化左子树
        if(p->lChild== nullptr){// 当前结点的左子树为空
            p->lChild =pre;//建立当前结点的前驱线索
            p->lTag = 1;
        }
        if(pre!= nullptr&&pre->rChild== nullptr){//前驱结点非空且其右子树为空
            pre->rChild = p;//建立前驱结点的后继线索
            pre->rTag=1;
        }
        pre=p;//标记当前结点成为刚刚访问过的结点
        InThread(p->rChild,pre);//递归,线索化右子树
    }
}

/**
 * 中序线索二叉树的建立
 * @param T
 */
void CreateInThread(ThreadTree T){
    ThreadTree  pre = nullptr;
    if(T!= nullptr){
        InThread(T,pre);//非空二叉树,线索化
        pre->rChild = nullptr;//处理遍历的最后一个结点
        pre->rTag = 1;
    }
}

/**
 * 求中序线索二叉树的中序序列的第一个结点
 * @param p
 * @return
 */
ThreadNode *FirstNode(ThreadNode *p){
    while (p->lTag == 0)p=p->lChild;//最左下结点(不一定是叶结点)
    return p;
}

/**
 * 求中序线索二叉树结点p的后继
 * @param p
 * @return
 */
ThreadNode *NextNode(ThreadNode *p){
    if(p->rTag == 0)return FirstNode(p->rChild);//右子树中最左下结点
    else return p->rChild;
}

void InOrder(ThreadNode *T){
    for(ThreadNode *p= FirstNode(T);p!= nullptr;p= NextNode(p))
        visit(p);
}
ThreadNode  *pre = nullptr;

//先序线索化二叉树
void CreatePreThread(ThreadTree T){
    pre= nullptr;
    if(T!= nullptr){
        InThread(T);
        if(pre->rChild == nullptr)pre->rTag = 1;//处理最后一个结点
    }
}
//遍历二叉树,边遍历边线索化
void InThread(ThreadTree T){
    if(T!= nullptr){
        InThread(T->lChild);
        visit(T);
        InThread(T->rChild);
    }
}

void visit(ThreadNode *q){
    if(q->lChild == nullptr){
        q->lChild = pre;
        q->lTag = 1;
    }
    if(pre!=nullptr &&q->rChild == nullptr){
        pre->rChild = q;
        pre->rTag = 1;
    }
    pre = q;
}
int main() {

    return 0;
}
